package com.rp.data.tcp_ws.server_tcp.echo;

import java.util.Random;

public class TopK {

    public static void main(String[] args) {

        float[] scores = new float[50000];
        int length = scores.length;
        Random random = new Random(1);

        for (int i = 0; i < length; i++) {
            scores[i] = random.nextFloat();
        }
        System.out.println(top_k(scores, 1));

        int total = 0;

        for (int i = 0; i < 10; i++) {
            long start = System.nanoTime();
            System.out.println(top_k(scores, i+1));
            long end = System.nanoTime();
            total += (end - start);
        }
        System.out.println(total/1000000);

    }

    private static int partion(float[] array, int low, int high) {

        float mid = array[low];
        while (low < high) {
            while (low < high && array[high] >= mid)
                high--;
            array[low] = array[high];
            while (low < high && array[low] <= mid)
                low++;
            array[high] = array[low];
        }
        array[low] = mid;
        return low;
    }

    private static float top_k(float[] array, int k) {

        if (array == null || array.length == 0)
            return -1;
        if (k < 0 || k > array.length - 1)
            return -1;
        int low = 0, high = array.length - 1;
        int index = partion(array, low, high);
        while (index != k) {
            if (index > k) {
                high = index - 1;
                index = partion(array, low, high);

            } else {
                low = index + 1;
                index = partion(array, low, high);
            }
        }
        return array[index];
    }
}
